package main

import "fmt"

type TreeNode struct {
	Value any
	Left  *TreeNode
	Right *TreeNode
}

/*
 * 二叉树前序遍历   根-> 左-> 右
 */
func (root *TreeNode) preorderTraversal(result *[]any) {
	if root == nil {
		return
	}
	*result = append(*result, root.Value)
	if root.Left != nil {
		root.Left.preorderTraversal(result)
	}
	if root.Right != nil {
		root.Right.preorderTraversal(result)
	}
}

/*
 *  二叉树中序遍历   左-> 根-> 右
 */
func (root *TreeNode) inorderTraversal(result *[]any) {
	if root == nil {
		return
	}
	if root.Left != nil {
		root.Left.inorderTraversal(result)
	}
	*result = append(*result, root.Value)
	if root.Right != nil {
		root.Right.inorderTraversal(result)
	}
}

/*
 *  二叉树后序遍历   左-> 右-> 根
 */
func (root *TreeNode) postorderTraversal(result *[]any) {
	if root == nil {
		return
	}
	if root.Left != nil {
		root.Left.postorderTraversal(result)
	}
	if root.Right != nil {
		root.Right.postorderTraversal(result)
	}
	*result = append(*result, root.Value)
}

// 二叉树层序遍历数组转树
func BuildTree(values []any) *TreeNode {
	if len(values) == 0 {
		return nil
	}

	var nodes = make([]*TreeNode, 0, len(values))
	for _, value := range values {
		if value == nil {
			nodes = append(nodes, nil)
		} else {
			node := &TreeNode{Value: value}
			nodes = append(nodes, node)
		}
	}

	var level = 0 // 层级，从0开始
	var stop = false
	var curIndex = 0

	for !stop {
		var levelCount = 1 << level            // 当前层级有多少节点
		var childIndex = curIndex + levelCount // 子节点的下标

		// 处理一整层的节点，把子节点挂到父节点
		for i := 0; i < levelCount && !stop; i, curIndex = i+1, curIndex+1 {
			if nodes[curIndex] == nil {
				childIndex += 2
				continue
			}

			if childIndex >= len(nodes) {
				stop = true
				break
			}

			nodes[curIndex].Left = nodes[childIndex]
			childIndex++
			if childIndex >= len(nodes) {
				stop = true
				break
			}

			nodes[curIndex].Right = nodes[childIndex]
			childIndex++
		}

		level++
	}

	return nodes[0]
}

func main() {
	root := randomBuild()

	var arr1 = new([]any)
	root.preorderTraversal(arr1)
	fmt.Println(" preorderTraversal:", arr1)

	var arr2 = new([]any)
	root.inorderTraversal(arr2)
	fmt.Println("  inorderTraversal:", arr2)

	var arr3 = new([]any)
	root.postorderTraversal(arr3)
	fmt.Println("postorderTraversal:", arr3)
}

/**
 *                      1
 *                  /       \
 *                 2            3
 *              /   \           /   \
 *             4     5         6     7
 *             /                \
 *             8                 9
 */
func randomBuild() *TreeNode {
	//var node8 = TreeNode{8, nil, nil}
	//var node9 = TreeNode{9, nil, nil}
	//var node7 = TreeNode{7, nil, nil}
	//var node6 = TreeNode{6, nil, &node9}
	//var node5 = TreeNode{5, nil, nil}
	//var node4 = TreeNode{4, &node8, nil}
	//var node3 = TreeNode{3, &node6, &node7}
	//var node2 = TreeNode{2, &node4, &node5}
	//var node1 = TreeNode{1, &node2, &node3}
	//return &node1

	return BuildTree([]any{1, 2, 3, 4, 5, 6, 7, 8, nil, nil, nil, nil, 9})
}
